lib/Mi manual de algoritmos/version_actual/src/grafos/prim.cpp

   1 //Complejidad: O(E log V)
   2 //¡El grafo debe ser no digirido!
   3 typedef string node;
   4 typedef pair<double, node> edge;
   5 //edge.first = peso de la arista, edge.second = nodo al que se
   6 //dirige
   7 typedef map<node, vector<edge> > graph;
   8
   9 double prim(const graph &g){
  10   double total = 0.0;
  11   priority_queue<edge, vector<edge>, greater<edge> > q;
  12   q.push(edge(0.0, g.begin()->first));
  13   set<node> visited;
  14   while (q.size()){
  15     node u = q.top().second;
  16     double w = q.top().first;
  17     q.pop(); //!!
  18     if (visited.count(u)) continue;
  19     visited.insert(u);
  20     total += w;
  21     vector<edge> &vecinos = g[u];
  22     for (int i=0; i<vecinos.size(); ++i){
  23       node v = vecinos[i].second;
  24       double w_extra = vecinos[i].first;
  25       if (visited.count(v) == 0){
  26         q.push(edge(w_extra, v));
  27       }
  28     }
  29   }
  30   return total; //suma de todas las aristas del MST
  31 }